<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title>友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="YOUZHILANE" />
  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/" />
<link href="%7balternate%20%7bRSS%20application/rss&#43;xml%20%20index%20alternate%20%20false%20false%20true%20false%20false%200%7d%20/youzhilane/index.xml%20https://yixy.github.io/youzhilane/index.xml%7d" rel="alternate" type="application/rss+xml" title="友知弄" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="友知弄" />
<meta property="og:description" content="YOUZHILANE" />
<meta property="og:type" content="website" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/" />

<meta property="og:updated_time" content="2019-11-17T00:22:22+08:00" />
<meta itemprop="name" content="友知弄">
<meta itemprop="description" content="YOUZHILANE">

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="友知弄"/>
<meta name="twitter:description" content="YOUZHILANE"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item active">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          
<section id="posts" class="posts">
  
  
    
  
  
  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B05%E5%88%86%E5%B1%82%E5%AD%98%E5%82%A8%E4%BD%93%E7%B3%BB/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 16 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      OS笔记(5)——分层存储体系 我们希望拥有一个私有的、无限大容量的、速度无限快的，断电不会丢失数据，并且价格低廉的存储器——但很遗憾，目前没有这样的内存。
1. 存储分层体系 目前计算机系统使用的存储体系是一种分层存储器体系。在该体系中，由上到下，速度越来越慢，价格越来越低。
 寄存器 cache 内存 磁盘 光盘、磁带  注意，register和cache的管理都由硬件来完成，换句话说，register/cache同内存之间的数据交换对所有程序员都是透明的；内存的管理由硬件和操作系统来完成，即内存同磁盘、光盘、磁带等低速设备之间的数据交换对应用程序员是透明的；磁盘等低速非易失性存储器的管理则被抽象称为文件进行管理，文件模型对应用程序员来说是可见的。
2. 内存 计算机硬件由三部分组成：CPU、存储器、I/O设备。这里提到的存储器指的实际上是内存。磁盘、光盘、磁带等低速存储设备则常被用于存放程序的输入或者输出数据。
相关链接 参考组成原理相关内容
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B05%E5%88%86%E5%B1%82%E5%AD%98%E5%82%A8%E4%BD%93%E7%B3%BB/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B06%E5%86%85%E5%AD%98%E7%9A%84%E6%8A%BD%E8%B1%A1%E4%B8%8E%E7%AE%A1%E7%90%86/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 66 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      OS笔记(7)——内存的抽象与管理 由于register和cache的管理由硬件完成，所以我们由内存管理开始我们对操作系统存储管理的介绍。
1. 无内存抽象 最早的内存管理是直面物理内存的，即没有内存抽象。此时的内存组织方式出现过以下几种。
 “用户程序+RAM”：用于大型机和小型机。 “ROM+用户程序”：用于掌上设备或嵌入式设备。 “ROM+用户程序+RAM”：用于早期PC。  直接使用物理内存面临两个问题，第一，用户可以寻址内存的每个字节，导致系统可以很容易地被（故意或偶然地）破坏，（除非使用特殊的硬件保护，如IBM360的锁键模式）；第二，系统想要并发运行多道程序是很困难的。
2. 内存抽象：虚拟地址空间 用户程序在运行时其实不希望介入到复杂的存储器管理过程中，作为普通的程序，它需要的是一个简单的执行环境，有一个单一的地址空间、有自己的CPU，好像整个程序占有整个计算机而不用关心其它的程序（当然程序间通信的部分除外，因为这是程序主动要求跟其它程序通信和联系）。进程模型是对CPU的一个抽象，而地址空间则为程序创造了一种抽象的内存。
 虚拟地址空间：虚拟地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的虚拟地址空间，并且这个虚拟地址空间独立于其它进程的地址空间（除了在一些特殊情况下进程需要共享它们的地址空间外）。  进程的虚拟地址并不是直接被送到内存总线上，而是被送到内存管理单元（MMU），MMU把虚拟地址映射为物理内存地址。
3. 内存地址重定位 可以采用重定位技术以支持多道程序在系统中运行。其中，动态重定位技术还提供了地址保护机制。
 静态重定位：指在程序执行之前，在装载过程中完成程序地址重定位。在程序装载到内存时，系统为每个程序地址加上一个偏移量常数。 动态重定位：指在程序运行中进行地址重定位。当一个进程运行时，程序在内存中的起始物理位置读取到基址寄存器中，程序的长度读取到界限寄存器中。进程每次访问内存时，CPU硬件会在把地址发送到内存总线前，自动把基址值加到进程发出的地址上，同时检查程序提供的地址是否合法（是否超过界限值）。  静态重定位方式会减慢装载速度，并且没有地址保护机制。动态重定位具有地址保护机制，但是每次访问内存时需要进行加法和比较运算（加法在不使用特殊电路时会很慢），导致重定位效率低下。
4. 交换（swap）技术 如果计算机物理内存足够大，可以保存所有进程，那么使用地址空间抽象并运用内存地址重定位技术似乎已经可以解决所有问题了。但实际上，所有进程所需的内存数量总是远远超出存储器能够支持的范围的。可以使用交换技术解决内存超载的问题。
 交换（swapping）技术：一个进程在内存中运行一段时间后，再将该进程保存到磁盘。这样，不在运行的进程就不会占用内存了。  交换会在内存中产生很多空洞（hole）区域。可以采用内存紧缩的技术解决这种碎片化的空洞区，但是这个操作会耗费大量的CPU时间，所以通常情况下是不会进行的。
 内存紧缩（memory compaction）：通过把所有的进程尽可能向某个方向移动，可能将小的空洞合成一大块，该技术被称为内存紧缩。  许多程序设计语言允许从堆中动态地分配内存，那么当进程空间试图增大时，交换技术可能会面临问题。为增长预留空间是一个解决方案。
5. 虚拟内存技术：分页 前面说过，重定位的效率不高，实际上该技术在内存管理上已经不太常用了。而交换技术也面临着进程空间膨胀的难题。虚拟内存技术是另一种可以解决内存超载问题的技术。该策略甚至能使程序在只有一部分被调入内存的情况下运行。
 虚拟内存（virtual memory）技术：将进程的虚拟地址空间分割成多个块，每块被称作一个页面（page）。每一页有连续的地址范围。这些页面被映射到物理内存（在物理内存中对应的单元称为页框page frame），但并不是所有的页面都必须在内存中才能运行程序。当进程引用到一部分在物理内存的页面时，由硬件立刻执行必要的映射。当进程引用到一部分不再物理内存的页面时，指令执行失败，进程陷入缺页中断，由OS负责将缺失的部分装入物理内存并重新执行失败的指令。内存和磁盘之间的交换总是以正规页面为单元进行的。  页面的大小一般从512B到64KB。
 页表：页表是一个数据结构，其目的是把page映射为page frame。从数学角度说，页表是一个函数，它的参数是虚拟页号，结果是page frame。注意，每个进程都拥有自己的页表。  上图展示了虚拟地址（虚拟页号+页内偏移量）通过页表转换为物理地址（页框号+页内偏移量）的过程。
在分页式系统中，有两个问题需要考虑：虚拟地址到物理地址的映射必须非常快；需要考虑应对虚拟地址空间很大的情况。
5.1 加速分页过程：TLB
通常，页表被设计在内存中，每次虚拟地址到物理地址的映射都必须访问内存，这样会导致性能低下。考虑将页表使用一组硬件快速寄存器实现是一种思路，但是考虑到昂贵的代价显然不可能将每个进程的页表都用这种方式实现。一个显而易见的方案是，使用一组硬件寄存器组成单一的页表，当启动一个进程时，操作系统将该进程在内存中的页表副本载入寄存器中。这样，该进程的地址映射过程中不再需要访问内存中的页表了，但是这样又增加了进程间切换时的开销。目前，一种常见的解决方案是使用TLB。
 TLB（Translation Lookaside Buffer，转换检测缓冲区）：“大多数程序总是对少量的页面进行多次访问”，基于这样的思想，在MMU中设置一个小型的硬件设备，它包含少量的表项，该设备就是TLB。地址映射首先在TLB中由硬件进行转换，如果TLB中匹配不到才会到去访问内存表项。  注意，最初，对TLB的管理和TLB失效处理都完全由MMU硬件来实现，只有在内存中没有找到某个页面时，才会陷入到操作系统中。后来，很多机器的几乎所有的页面管理都在软件中实现了。这些机器上，TLB表项被显示地装载。当发生TLB访问失效的时候不再是MMU到页表中查找并取出数据，而是生成一个TLB失效并将问题提交给操作系统解决。事实证明，如果TLB大（比如64个表项）到可以减少失效率，TLB的软件管理也能够变得足够有效。
5.2 处理巨大的虚拟地址空间：多级页表与倒排页表
以32位虚地址为例，后12位为偏移量，则页面大小为4KB，页面数量为2^20。
采用“多级页表”的原因是避免把全部页表一直保存在内存中，那些从不需要的页表项将被存储在磁盘。一般，页表级数不超过4级。
当虚拟地址空间是2^64字节时（64位计算机），假设页面大小是4KB，需要有2^52个表项。即使采用了多级页表，存储在磁盘上的表项数据所占用的空间也是巨额的。此时，解决方案之一是使用倒排页表（invertered page table）。在这种设计之中，实际内存里每一个页框有一个表项，而不是每一个虚拟页面有一个表项。
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B06%E5%86%85%E5%AD%98%E7%9A%84%E6%8A%BD%E8%B1%A1%E4%B8%8E%E7%AE%A1%E7%90%86/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B07%E5%86%85%E5%AD%98%E5%8A%A8%E6%80%81%E5%88%86%E9%85%8D%E7%AE%97%E6%B3%95/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 18 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
       OS笔记(8)——内存动态分配算法 在动态分配内存时，操作系统必须对其进行管理。一般而言，有两种方式跟踪内存使用情况，位图和空闲链表。
1. 使用位图的存储管理  位图：顾名思义，可以看成是一个bit表。内存可能被划分为几个字或几千字节的分配单元，每个分配单元对应位图中的一位，0表示空闲，1表示占用。  使用位图时的主要问题是，在决定分配k个单元时，系统必须对位图进行搜索，在其中找出有k个值连续为0的串，这是一个耗时的操作（因为位图中该串可能跨越字的边界）。
2. 使用链表的存储管理 使用链表的存储管理需要维护一个记录已分配内存和空闲内存的链表。
 已分配内存链表：链表中一个节点包含一个进程所占据的内存区。 空闲内存链表：链表中一个节点包含两个进程之间的一个空闲区。  使用链表数据结构时，常见的内存分配算法如下，仿真程序试验表明，后三种算法并不比首次适配算法更优秀。
 首次适配算法：从头开始搜索链表，直到找到足够大的空闲区，除非空闲区与待分配空间大小一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。 下次适配算法：与首次适配算法方式基本相同。区别在于，每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从该位置开始搜索。（bays 1977 的仿真程序证明下次适配算法性能略低于首次适配算法） 最佳适配算法：每次搜索整个链表，找出能够分配的最小的空闲区进行分配。 最差适配算法：每次搜索整个链表，找出能够分配的最大的空闲区进行分配。  
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B07%E5%86%85%E5%AD%98%E5%8A%A8%E6%80%81%E5%88%86%E9%85%8D%E7%AE%97%E6%B3%95/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B08%E5%86%85%E5%AD%98%E9%A1%B5%E9%9D%A2%E7%BD%AE%E6%8D%A2%E7%AE%97%E6%B3%95/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 67 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
      OS笔记(8)——内存页面置换算法 发生缺页中断时，OS必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果该页面没有被修改过，那么它的磁盘上的副本不需要被回写，直接使用调入的页面覆盖原有页面就行了。
最好的两种算法是老化算法和工作集时钟算法，它们分别基于LRU和工作集，具有良好的页面调度性能，可以有效的实现。
1. 最优页面算法 该算法是可以给出的最好的页面算法，遗憾的是该算法不可能实现。
 最优页面算法：假设每个页面都可以用在该页面首次被访问前要执行的指令数作为标记，该算法规定应置换标记最大的页面。  2. 最近未使用页面置换算法（Not Recently Used） 当启动一个进程时，操作系统为其每个页面设置两个状态位R和W（其初始值为0）：页面被访问时设置R位为1，页面被修改时设置W位为1。
注意，R位定期（比如时钟中断）会被清0，以区别最近没有被访问的页面和被访问的页面。
页面根据其R和W值可被分为四类：
1 2 3 4  第0类：R=0，M=0 第1类：R=0，M=1 第2类：R=1，M=0 第4类：R=1，M=1    NRU算法：随机地从类编号最小的非空类中挑选一个页面淘汰之。  NRU算法可以看做是LRU算法的一个粗糙的实现。
3. 先进先出算法（First In First Out） 操作系统维护一个队列（通常是链表），存放内存中的页面，每次淘汰队首的页面，将最新进入的页面放到队尾。
因为可能抛弃重要页面，所以该算法一般不会单独使用。
4. 第二次机会页面置换算法（second chance） 第二次机会页面置换算法是FIFO算法的升级版。
 第二次机会算法：对FIFO进行了简单的修改，在淘汰页面时，会判断该页R位是否被设置，若R位没被设置则淘汰该页面，否则将该页面R位清0，并且将其放入队尾，然后重新在队首进行搜索。  5. 时钟页面置换算法（clock） clock算法是对FIFO和第二次机会算法的一个优化，使用环形链表实现数据结构，避免在链表中移动页面，减少不必要的开销。
6. 最近最少使用页面置换算法（Least Recently Used） 对最优页面置换算法的一个很好的近似是基于这样的观察：在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内仍然不会被使用。
 LRU算法：在缺页中断发生时，置换掉未使用时间最长的页面。  虽然LRU在理论上是可以实现的，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作，即使使用硬件实现也一样费时（假设有这样的硬件）。
 然而，还是有一些使用特殊硬件实现LRU的方法。首先考虑一个最简单的近似方法，这个方法要求硬件有一个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。（这看起来实际上是一个硬件版本的NUR算法）
现在让我们看一看第二个硬件实现的LRU算法。在一个有n个页框的机器中，LRU硬件可以维持一个初值为0的n×n位的矩阵。当访问到页框k时，硬件首先把k行的位都设置成1，再把k列的位都设置成0。在任何时刻，二进制数值最小的行就是最近最少使用的，第二小的行是下一个最近最少使用的，以此类推。
 前面两种LRU算法虽然在理论上都是可以实现的，但只有非常少的计算机拥有这种硬件。因此，需要一个能用软件实现的解决方案。
7. 使用软件模拟LRU：NUR 和 老化算法 只有非常少的计算机支持硬件实现LRU。因此，需要考虑一个能够使用软件实现的解决方案。
 NFU（Not Frequently Used，最不常用）算法：该算法将每个页面与一个软件计数器相关联，计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它的值是0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。NFU的主要问题是它“从来不忘记任何事情”。 老化算法：老化算法对NFU进行了修正。首先，在R位被加进之前先将计数器右移一位；其次，将R位加到计数器最左端的位而不是最右端的位。发生缺页中断时，将置换计数器值最小的页面。  8.
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B08%E5%86%85%E5%AD%98%E9%A1%B5%E9%9D%A2%E7%BD%AE%E6%8D%A2%E7%AE%97%E6%B3%95/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
    <article class="post bg-white">
  <header class="post-header">
    <h1 class="post-title">
      
      <a class="post-link" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B09%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/"></a>
    </h1>
    
    <div class="post-meta">
      <time datetime="0001-01-01" class="post-time">
        0001-01-01
      </time>
      
      <span class="more-meta"> 约 31 字 </span>
      <span class="more-meta"> 预计阅读 1 分钟 </span>
      
      
      
    </div>
  </header>
  
  <div class="post-content">
    
    <div class="post-summary">
       OS笔记(9)——文件系统 文件是对IO的抽象。程序在进行输入输出时，是以文件为单位的。
 文件系统（file system）：操作系统中处理文件的部分称为文件系统。  1. 文件 文件命名规则在各个OS中不尽相同。需要注意的一点是，Unix-like文件系统是区分大小写的，MS-DOS则是不区分大小写的。
文件可以有多种构造方式，常见的一种文件结构实现是采用无结构的字节序列，OS实际上不知道也不关心文件的内容是什么，OS所见到的就是字节，其任何含义只在用户程序中解释。在Unix和Windows中都采用这种方法。
很多OS支持多种文件类型，如普通文件、目录文件等。普通文件包含有用户信息（一般分为ASCII和二进制文件），目录则是管理文件系统结构的系统文件。
大多数OS使用目录树来组织文件系统，此时需要某种方法指明文件。常用的方法有两种。
 绝对路径：从根目录到文件的路径组成。 相对路径：相对于当前进程工作目录的一个路径。  2. 文件系统的实现 1.文件系统布局
文件系统存放在磁盘上。多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。
 主引导记录(Master Boot Record, MBR)：位于磁盘的0号扇区，由BIOS读入并执行；作用是确定活动分区，读入并执行其引导块，引导块中的程序装载该分区的操作系统。 分区表：位于MBR结尾，其作用是给出每个分区的起始和结束地址。 引导块：每个分区都是从一个引导块开始，即使它不含有一个可启动的操作系统。  除了从引导块开始之外，磁盘分区的布局是随着文件系统的不同而变化。文件系统经常包含有如下项目：
 超级块：包含文件系统的所有关键参数，在计算机启动或该文件系统首次使用时，把超级块读入内存。超级块的典型信息包括：确定文件系统类型用的魔数、文件系统中的数据块的数量以及其他重要的管理信息。 空闲空间管理：管理空闲块信息，例如可以用位图或者链表的形式记录。 i节点：一个数据结构数据，每个文件一个，i节点说明了文件的方方面面。后面会重点谈到。 根目录：存放文件系统目录树的根部。 文件和目录：就是存放其他所有的目录和文件。  2.文件存储实现
前面说过，文件对于大多数操作系统来说就是一个字节序列，这是其逻辑上的结构。对于文件的存储实现，有以下几种。
 连续分配：最简单的分配方案是把每个文件作为一连串连续数据块存储到磁盘上。  
    </div>
    <div class="read-more">
      <a href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/os%E7%AC%94%E8%AE%B09%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/" class="read-more-link">阅读全文</a>
    </div>
    
  </div>
</article>

  
</section>






  
  
  

  
  

  
  

  
  

  
  

    <nav class="pagination">
      <ul>

      
      
      <li><a href="/youzhilane/">««</a></li>
      

      
      
      <li><a href="/youzhilane/page/7/">«</a></li>
      

      
      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/2/">
              2
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/3/">
              3
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/4/">
              4
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/5/">
              5
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/6/">
              6
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/7/">
              7
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="active">
            <a href="/youzhilane/page/8/">
              8
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/9/">
              9
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/10/">
              10
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/11/">
              11
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/12/">
              12
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/13/">
              13
            </a>
          </li>
        

      

        

        
        

          
          
          

            
              
            

          

        
        

        
        
          <li class="">
            <a href="/youzhilane/page/14/">
              14
            </a>
          </li>
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

        

        
        

          
          
          

            

          

        
        

        
        

      

      
      
      <li><a href="/youzhilane/page/9/">»</a></li>
      

      
      
      <li><a href="/youzhilane/page/19/">»»</a></li>
      

      </ul>
    </nav>
  





        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
